package 题目集.动态规划.最长递增子序列;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
 * 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 * 注意 这个数列必须是 严格 递增的。
 */
public class ch07_最长上升子序列个数2 {
    int[] counts;
    int[] dp;

    /**
     * 朴素做法：
     *  这题相当于在传统lis上加了一个 个数限制
     *  设dp[i]为以i结尾，有多少个最长递增子序列。
     *  那结果为左侧所有比nums[i]小，且长度最长的所有dp[k]之和
     *  n^2复杂度
     */
    public int findNumberOfLIS(int[] nums) {
        dp = new int[nums.length];
        counts = new int[nums.length];
        counts[0] = 1;
        dp[0] = 1;
        int maxLen = 1;  //当前最长长度
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 0;      //比它小的最大长度
            int sumK = 0;   //比它小的dp[k]之和
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    if (dp[j] > dp[i]) {
                        dp[i] = dp[j];
                        sumK = counts[j];
                    } else if (dp[j] == dp[i]) {
                        sumK += counts[j];
                    }
                }
            }
            dp[i]+=1;
            counts[i] = Math.max(sumK, 1);
            maxLen = Math.max(maxLen, dp[i]);
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] == maxLen) {
                res += counts[i];
            }
        }
        return res;
    }

    @Test
    public void test() {
        int[] arr = {1, 4, 3, 5, 4, 7};
        int numberOfLIS = findNumberOfLIS(arr);
        System.out.println(numberOfLIS);
    }
}
